package util

import java.util

import scala.collection.mutable
import scala.collection.mutable.ArrayBuffer


object Solution1 {





  def threeSum(nums: Array[Int]): List[List[Int]] = {
    val list = scala.collection.mutable.ArrayBuffer.empty[List[Int]]

    val nums2 = nums.sorted
    var sum = 0
    for (i <- 0 until nums2.length - 2) {
      var left = i + 1
      var right = nums2.length - 1
      while (left < right) {
        if (i > 0 && nums2(i) == nums2(i - 1)) right = 0
        else {
          sum = nums2(i) + nums2(left) + nums2(right)
          if (sum == 0) {
            val one = List(nums2(i), nums2(left), nums2(right))
            list += one
            left += 1
            right -= 1
            while (left < right && nums2(left) == nums2(left - 1)) {
              left += 1
            }
            while (left < right && nums2(right) == nums2(right + 1)) {
              right -= 1
            }
          } else if (sum < 0) left += 1
          else right -= 1
        }

      }
    }
    list.toList
  }

  def threeSumClosest(nums: Array[Int], target: Int): Int = {
    val nums2 = nums.sorted
    var closest = Integer.MAX_VALUE
    var res = 0
    for (i <- 0 until nums2.length - 2) {
      var left = i + 1
      var right = nums2.length - 1
      while (left < right) {
        val sum = nums2(i) + nums2(left) + nums2(right)
        if (sum > target) {
          if (sum - target < closest) {
            closest = sum - target
            res = sum
          }
          right -= 1
        } else if (sum < target) {
          if (target - sum < closest) {
            closest = target - sum
            res = sum
          }
          left += 1
        } else {
          return target
        }
      }
    }
    res
  }


  import java.util

  def letterCombinations(digits: String): List[String] = {
    val result = ArrayBuffer.empty[String]
    if(digits.size ==0)  return result.toList
    val map = new Array[String](10)
    map(0) = ""
    map(1) = ""
    map(2) = "abc"
    map(3) = "def"
    map(4) = "ghi"
    map(5) = "jkl"
    map(6) = "mno"
    map(7) = "pqrs"
    map(8) = "tuv"
    map(9) = "wxyz"
    val middleTemp = new Array[Char](digits.length)
    dfsGetStr(digits, 0, middleTemp, map, result)
    result.toList
  }

  private def dfsGetStr(digits: String, index: Int, middleStr: Array[Char], map: Array[String], result: ArrayBuffer[String]):Unit = {
    if (index == digits.length) {
      result += new String(middleStr)
      return
    }
    val strChar = digits.charAt(index)
    var i = 0
    while (i < map(strChar - '0').length) {
      middleStr(index) = map(strChar - '0').charAt(i)
      dfsGetStr(digits, index + 1, middleStr, map, result)
      i += 1
    }
//    result
  }


  def isValid(s: String): Boolean = {
    val map = Map('('->')','['->']','{'->'}')
    val stk =  scala.collection.mutable.ArrayStack[Character]()
    var i=0
    while(i< s.length){
       s.charAt(i) match {
        case  '(' | '[' |'{'=> stk.push(s.charAt(i))
        case  ')' | ']' |'}'=> if(stk.isEmpty || map(stk.pop) != s.charAt(i) ) return false
        case _ =>
      }
      i += 1
    }
    stk.isEmpty
  }

  def removeDuplicates(nums: Array[Int]): Int = {
    if (nums.length == 0) return 0
    var current = 1
    var index = 1
    var pre = nums(0)
    while (index < nums.length) {
      if (!(nums(index) == pre)){
        nums( current ) = nums(index)
        current +=1
      }

      pre = nums(index)
      index += 1
    }
    current
  }

  def removeElement(nums: Array[Int], `val`: Int): Int = {
    var i = 0
    var n = nums.length
    while(i< n){
      if(nums(i) == `val`){
        nums(i) = nums(n-1)
        n -= 1

      }else{
        i+=1
      }
    }
    n

  }

  def removeNthFromEnd(head: ListNode, n: Int): ListNode = {
    val tem =  new ListNode(0)
    tem.next = head
    var length = 0
    var first = head
    while(first != null){
      length += 1
      first = first.next
    }
    length -= n
    first = tem
    while (length >0){
      length -= 1
      first = first.next
    }
    first.next = first.next.next

    tem.next
  }



  def permuteUnique(nums: Array[Int]): List[List[Int]] = {
    val res =  scala.collection.mutable.ArrayBuffer.empty[List[Int]]
    val len = nums.length
    if (len == 0 || nums == null) return res.toList
    val used = new Array[Boolean](len)
    // 采用前后元素交换的办法，dfs解题
    java.util.Arrays.sort(nums);
    exchange(nums, 0, len, res,used)
    res.toList
  }

  def exchange(nums: Array[Int], i: Int, len: Int, res:scala.collection.mutable.ArrayBuffer[List[Int]],used:Array[Boolean]): Unit = { // 将当前数组加到结果集中
    if (i == len - 1) {
      val list = scala.collection.mutable.ArrayBuffer.empty[Int]
      var j = 0
      while (j < len) {
        list += nums(j)
        j += 1
      }
      res += list.toList
      return
    }
    // 将当前位置的数跟后面的数交换，并搜索解
    var j = i
    while (j < len) {
      if( !used(j) &&(j == 0 || nums(j) != nums(j - 1) || used(j-1) )){
        used(j) = true
        swap(nums, i, j)

        exchange(nums, i + 1, len,res,used)

        swap(nums, i, j)
        used(j) = false
      }

      j += 1
    }
  }

  def swap(nums: Array[Int], i: Int, j: Int): Unit = {
    val temp = nums(i)
    nums(i) = nums(j)
    nums(j) = temp
  }


  def main(args: Array[String]): Unit = {
    //            val nums = Array(0,0,0)

    val l1 =new ListNode(1)
    val l2 =new ListNode(2)
    val l3 =new ListNode(3)
    val l4 =new ListNode(4)
    val l5 =new ListNode(5)
    l1.next = l2
    l2.next = l3
    l3.next = l4
    l4.next = l5
    val res = removeNthFromEnd(l1,2)
    println(res)

    val arr= Array(0,0,1,0,9)
    println(permuteUnique(arr))


  }


}
